COMMENT ⊗   VALID 00009 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Graph structure definitions
C00003 00003	.SBTTL GRAPH ROUTINES
C00004 00004	ROUTINE INVLDT,<ND>
C00005 00005	ROUTINE CHANGE,<ND,VNEW>
C00007 00006	ROUTINE GETVAL,<ND>
C00008 00007	ROUTINE EVALND,<ND,T>
C00010 00008	ROUTINE ADDCLC,<ND,CLC>
C00011 00009	GET2WD & GET3WD (eventually go somewhere else)
C00013 ENDMK
C⊗;
;Graph structure definitions
;RHT 9/74

;CELL LINKS
	II==0
	XX	DATUM
	XX	LINKF
	XX	LINKB

;GRAPH NODES
	II==0
	XX	NXTGN		;CHAIN OF ALL GNODES IN THE WORLD
	XX	PRVGN
	XX	INVMRK		;USED AS FLAG
	XX	GNVAL		;POINTER AT VALUE
	XX	GNDEPS		;DEPENDENT GRAPH NODES
	XX	GNCLCS		;CALCULATOR LIST (DBL LINKED)
	XX	GNCHGS		;CHANGE LIST

;CALCULATOR CELL
	II==0
	XX	NXTCLC		;LIST LINK
	XX	NEEDED		;LIST OF NEEDED NODES
	XX	FORM		;SOME SORT OF CODE TO EVAL

;CHANGER CELL
	II==0
	XX	NXTCHG
	XX	CHGCOD

.SBTTL GRAPH ROUTINES
;MINOR ROUTINE:
;
;	JSR	PC,NXTTIM
;	
;RETURNS TIME←TIME+1 IN R0
;IF TIME GOES NEGATIVE THEN GOES THRU & SETS ALL POSITIVE MARK
;CELLS TO NEGATIVE, & THEN SETS TIME TO 1

TIME:	0
GNODES:	0	;LIST OF ALL GRAPH NODES IN THE WORLD

NXTTIM:	INC	TIME		;TIME←TIME+1
	MOV	TIME,R0
	BGT	TIME,NXT.RT	;OK?
	MOV	GNODES,R0	;
	BEQ	NXTT.3		;DID WE HAVE ANY??
NXTT.1: TST	INVMRK(R0)	;YES
	BLE	NXTT.2		;WAS INVMRK POSITIVE
	NEG	INVMRK(R0)	;YES, NEGATE IT
NXTT.2:	MOV	NXTGN(R0),R0	;GO ON TO NEXT
	BNE	NXTT.1		;IF ANY
NXTT.3:	INC	R0		;R0←0+1
	MOV	R0,TIME		;TIME IS 1 AGAIN
NXT.RT:	RTS	PC

ROUTINE INVLDT,<ND>
	MOV	ND(RF),R0
	JSR	PC,INVLR0
	RTS	RF

INVLR0:	TST	INVMRK(R0)	;IS IT DEAD YET?
	BNE	INVL.R		;ALREADY INVALID??
INVL.1:	DEC	INVMRK(R0)	;NO, MAKE IT SO
	MOV	R2,-(SP)	;SAFE REGISTER
	MOV	GNDEPS(R0),R2	;DEPENDENTS
	BEQ	INVL.X		;IF ANY 
INVL.2:	MOV	DATUM(R2),R0	;GET A DEPENDENT
	JSR	PC,INVLR0	;AND INVALIDATE IT
	MOV	LINKF(R2),R2	;GO TO NEXT
	BNE	INVL.2		;IF ANY
INVL.X:	MOV	(SP)+,R2	;GET BACK SCRATCH REGISTER
INVL.R:	RTS	PC

ROUTINE CHANGE,<ND,VNEW>
	MOV	ND(RF),R0	;THE NODE
	JSR	PC,INVLR0	;INVALIDATE IT
	MOV	ND(RF),R0	;SINCE NO PROMISES WERE MADE
	MOV	R2,-(SP)	;SAVE A COUPLE REGISTERS
	MOV	R3,-(SP)
	MOV	GNVAL(R0),R2	;OLD VALUE
	MOV	VNEW(RF),GNVAL(R0) ;PUT AWAY NEW VALUE
	MOV	GNCHGS(R0),R3	;CHANGERS
	BEQ	CH.XXX		;MAY BE ABOUT DONE
CH.1:	CALL	CRTS,<R2,VOLD(RF)> ;***** ACTUALLY MUST CALL A CHANGE ROUT HERE
	MOV	NXTCHG(R3),R3	;CDR DOWN LIST
	BNE	CH.1
CH.XXX:	MOV	ND(RF),R0
	CLR	INVMRK(R0)
	MOV	(SP)+,R3
	MOV	(SP)+,R2
CRTS:	RTS	RF
ROUTINE GETVAL,<ND>
	MOV	ND(RF),R0
	JSR	PC,GETVR0
	RTS	RF

GETVR0:	TST	INVMRK(R0)	;WAS IT VALID ALREADY
	BEQ	GETV.R		;JUST RETURN IF IT WAS
	MOV	R0,-(SP)	;SAVE EXTRA COPY FOR RANDOMNESS
	MOV	RF,-(SP)
	MOV	R0,-(SP)	;EVALNODE(ND,TIME←TIME+1)
	JSR	PC,NXTTIM	
	MOV	R0,-(SP)
	MOV	#MARK2,-(SP)
	MOV	SP,RF
	JSR	PC,EVALND		
	MOV	(SP)+,R0	;GET NODE BACK
GETV.R:	MOV	GNVAL(R0),R0	;GET THE VALUE CELL
	RTS	PC		;RETURN

ROUTINE EVALND,<ND,T>
	MOV	ND(RF),R0
	MOV	INVMRK(R0),R1	;IF INVMRK = 0 
	BEQ	EV.RTS		;THEN RETURN
	CMP	R1,T(RF)	;IF INVMRK=T
	BEQ	EV.RTS		;THEN RETURN
	MOV	R2,-(SP)	;SAVE REGISTERS
	MOV	R3,-(SP)
	MOV	GNCLCS(R0),R2	;CALCULATORS
	BEQ	EV.XXX		;IF ANY
EV.CLP:	MOV	NEEDED(R2),R3	;NEEDED LIST
	BEQ	EV.NOK		;ALL NEEDS MET YET?
EV.NLP: CALL	EVALND,<DATUM(R3),T(RF)> ;NO, GET NEXT
	MOV	DATUM(R3),R0	;SEE IF NEED WAS MET?
	TST	INVMRK(R0)	;DID WE WIN
	BNE	EV.NXC		;BRANCH IF STILL NOT VALID
	MOV	LINKF(R3),R3	;TRY NEXT NEEDED
	BNE	EV.NLP		
EV.NOK:	CALL	EVLCLC,<R2>	;EVALUATE CALCULATOR
	MOV	ND(RF),R1	;PICK UP ND
	MOV	R0,GNVAL(R1)	;SAVE VALUE IN IT
	CLR	INVMRK(R1)	;REVALIDATE THE NODE
	BR	EV.XXX		;EXIT
EV.NXC:	MOV	NXTCLC(R2),R2	;TRY NEXT CALCULATOR
	BNE	EV.CLP		;IF ANY TO TRY
EV.XXX:	MOV	(SP)+,R3	;RESTORE ACS
	MOV	(SP)+,R2
EV.RTS:	RTS	RF		;RETURN

ROUTINE EVLCLC,<CLC>
	RTS	RF
ROUTINE ADDCLC,<ND,CLC>
	MOV	R2,-(SP)	;SAVE A REGISTER
	MOV	R3,-(SP)	;SAVE A REGISTER
	MOV	ND(RF),R3	;THE NODE
	MOV	CLC(RF),R1	;THE CALCULATOR
	MOV	GNCLCS(R3),NXTCLC(R1) ;CURRENT CALCULATOR LIST
	MOV	NEEDED(R1),R2	;LIST OF NEEDED NODES
	BEQ	ACLC.X		;ALL DONE
ACLC.1:	JSR	PC,GET2WD	;GET A TWO-WORD CELL
	MOV	R3,DATUM(R0)	;THIS NODE IS NOW A DEPENDENT OF
	MOV	DATUM(R2),R1	;THE NEEDED NODE
	MOV	GNDEPS(R1),LINKF(R0) ;ADD IT TO THE DEPENDENTS LIST
	MOV	R0,GNDEPS(R1)	;
	MOV	LINKF(R2),R2	;NEXT NEEDED NODE
	BNE	ACLC.1		;
ACLC.X:	MOV	(SP)+,R3	;RESTORE ACS
	MOV	(SP)+,R2
	RTS	R5

;GET2WD & GET3WD (eventually go somewhere else)

W2SPC:	SPC	W2ID,MP2WD,2,20,1,20,25
W3SPC:	SPC	W3ID,MP3WD,3,20,1,20,25

MP2WD:	TSTB	TAG(R0)
	BNE	MPRTS		;ALREADY DID THIS ONE
	JSR	PC,@2(RF)	;
	MOV	R2,-(SP)	;
	MOV	R0,R2		;SAVE RESULT OF ROUT
MPDLF:	MOV	DATUM(R2),R0	;DO DATUM
	JSR	PC,MARKR0	;
	MOV	R0,DATUM(R2)	;
	MOV	LINKF(R2),R0	;DO LINKF
	JSR	PC,MARKR0	;A LONG LIST WILL PDLOV (ALAS)
	MOV	R0,LINKF(R2)	; BUT WE DONT HAVE ANY LONG LISTS (I HOPE)
	MOV	R2,R0		;RETURN VALUE
	MOV	(SP)+,R2	;
MPRTS:	RTS	PC

MP3WD:	TSTB	TAG(R0)		;DID WE DO THIS
	BNE	MPRTS		;YES
	JSR	PC,@2(RF)	;
	MOV	R2,-(SP)
	MOV	R0,R2
	MOV	LINKB(R2),R0	;DO LINKB
	JSR	PC,MARKR0
	MOV	R0,LINKB(R2)	;
	BR	MPDLF		;GO DO DATUM & LINKF

; GET A TWO-WORD CELL (OF POINTERS)
GET2WD:	MOV	#W2ID,R0
	JMP	GETBLK

GET3WD:	MOV	#W3ID,R0
	JMP	GETBLK